今天我們來看各家有什麼樣的資料結構來存放 Key-value pair 囉！而這樣的結構又是一對一的映射關係，也就是一個 Key 只會對到一個 Value。而我們要挑戰的題目也很簡單，先輸入一個數字告訴程式，接下來會有幾個名字 => 電話號碼的組合要輸入，都輸入完之後就開始輸入名字來找到剛才的電話號碼。如果打了一個沒有在裏頭的名字，就會顯示 Not found 並且結束程式。那就開始吧！
n = int(input())
d = dict()
for _ in range(0, n):
name, number = input().split()
d[name] = number
while True:
name = input()
if name in d:
print("{}={}".format(name, d[name]))
else:
print("Not found")
break
input() 接收 User input 後，並轉換成 int 存到 n ，這表示我們接下來要接收 n對 Key-value pair。 d = dict()，表示我們在這邊宣告 d是一個 Dictionary，就是 Python 內用來存放 K-V pair 的結構啦！(接下來會慢慢解釋)。接著我們透過 iterate range(0, n) ，這是 Python 常見的做法，因為 Python 沒有 C-style for-loop 所以 for _ in range(0, n) 表示我們接下來要做 n 次 code block 內的事情， _ 表示我們不 care range(0, n) 每次回傳什麼。 input().split() 是接收輸入並且以空白當作 separator 來把一個字串變成 list of string，例如 'abc def'.split() 會變成 ['abc', 'def'] ，而我們期望 User 輸入的就是 <name> <number> (以空格隔開)。而這個得到的 list 因為有兩個 elements，分別賦予給 name 跟 number 。 d[name] = number 就是說把 key 是 name 而 value 是 number 的 pair 存進這個 Dictionary。如果今天要取出來也是直接 d[name] 就可以得到 number 了，如果給了一個沒有在這個 Dictionary 的 Key 會怎樣呢？答案是會噴錯。 為了避免，可以使用 <dictionary>.get(<key>, <default>) ，此時如果 <key> 不在的話會回 None 或是 <default> 如果有定義的話。while ，這是一個無限迴圈，每次從 User input 接收一個要查詢的名字存到 name 。 name in d 可以讓我們知道 name 有沒有在 d 這個 dictionary 裏頭，有的話就返回 true，反之為 false。然後就是印出來啦！如果名字不在裏頭，就 break 結束迴圈。O(1)，不過當數量一多的時候可能就不是囉！(提示：實作上會有機會使用到 linked list)，想知道更多關於 Hash table 的可以參考這裡囉！import scala.io.StdIn
object Solution {
def main(args: Array[String]) {
val num = StdIn.readLine().toInt
def addNewKV(m :Map[String, String], remainNum: Int): Map[String, String] = {
if (remainNum == 0) m
else {
val keyAndValue = StdIn.readLine().split(" ")
addNewKV(m + (keyAndValue(0) -> keyAndValue(1)), remainNum - 1)
}
}
def searchMap(mapToBeSearched: Map[String, String]): Unit = {
val nameToSearch = StdIn.readLine()
mapToBeSearched.get(nameToSearch) match {
case Some(v) => {
println(s"$nameToSearch=$v")
searchMap(mapToBeSearched)
}
case None => System.exit(0)
}
}
val resultedMap = addNewKV(Map(), num)
searchMap(resultedMap)
}
}
Int 存到 num ，接下來我們有一個 Function 叫做 addNewKV ，是個遞迴函數，而且是 Tail recursion，第一個參數是目前的 Map (Key 跟 Value 的 Type 都是 String ( Map[String, String]))，而第二個參數 remainNum是現在還要接收幾次 User 的輸入。終止條件是發現 remainNum 為 0 的時候就回傳目前的 Map m 。如果 remainNum 不是 0 就先讀入 User input 並且透過 split(" ") ，來把一個 string 用 " " (也就是空白)，來切成 Array of string。再來就是把這個 Array of string 中的 Key ( keyAndValue(0)), value (keyAndValue(1)) 取出後跟 m 相加，也就是會得到一個新的 Map，包含本來的 m 以及剛取出的 K-V。接著把這個新的 Map，和 remainNum-1 當作參數再次執行 addNewKV 。最終這個遞迴函數結束就會得到最終的 Map 囉！searchMap 這個遞迴函數做的事情很簡單，就只是把剛才得到的 Map 用 User Input 的 Key (存到 nameToSearch)去找看看有沒有在 Map 裏頭。這裡我們找的方式是用 mapToBeSearched.get(nameToSearch) ，這裡會得到 Option type (之前 Rust 有介紹類似概念)，再來我們用 Pattern matching 的方式。要是 Key 有存在就回傳Some(value) ，然後我們就把 value 取出來並印出，再繼續執行 searchMap 。直到當我們輸入的 Key 不在 mapToBeSearched 內而得到 None 後，就退出程式囉！package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
func main() {
scanner := bufio.NewScanner(os.Stdin)
phonebook := make(map[string]string)
scanner.Scan()
num, _ := strconv.Atoi(scanner.Text())
for i := 0; i < num; i++ {
scanner.Scan()
record := strings.Split(scanner.Text(), " ")
phonebook[record[0]] = record[1]
}
for scanner.Scan() {
name := scanner.Text()
if v, ok := phonebook[name]; ok {
fmt.Printf("%v=%v\n", name, v)
} else {
fmt.Println("Not found")
}
}
}
make(map[string]string) 是在 Golang 去 new 出一個空的 Map (Key 是 string , value 是 string )。Scanner 的用法以前已經講過，這邊就不再贅述。User input 的值被讀進來之後存到 num 。接下來進到建置電話號碼的 Loop，把 User input 讀取進來後透過 strings.Split(scanner.Text, " ") 將字串以空白切開後存成 Array record 。接著就是 phonebook[record[0]] = record[1] 的方式來把 K-V 加到 Map phonebook 裏頭。最後的 For loop 是個無限迴圈，每次也都一樣先從 User input 讀取 ( scanner.Scan()) 並且存到 name ，接著 phonebook[name] 會去把 name 這個 Key 的值取出來。因為這裡 Golang 的 Error handling 不是用 Exception 的方式，而是透過回傳第二個參數來告訴你是不是有這個 Key，也就是這裡 ok 的值，他會是 True 或 False，所以如果 ok 是 true 就印出來不然就說 Not found 囉！make 也可以用 map[string]string{} 的方式來取得一個空的 Map。假使我們想要走訪一個 Map 內所有的 K-V pair 可以用下面的方式去走訪 Map m 。for key, value := range m {
fmt.Println("Key:", key, "Value:", value)
}
use std::collections::HashMap;
use std::str::FromStr;
use std::io::stdin;
fn main() {
let mut input = String::new();
stdin().read_line(&mut input).expect("Failed to read input");
let n = i32::from_str(input.trim()).expect("Failed to parse i32 from string");
let mut phone_book: HashMap<String, String> = HashMap::new();
for _ in 0..n {
let (name, number) = read_entry();
phone_book.insert(name, number);
}
while let Some(query) = read_query() {
match phone_book.get(&query) {
Some(number) => println!("{}={}", query, number),
None => println!("Not found")
}
}
}
type Entry = (String, String);
fn read_entry() -> Entry {
let mut input = String::new();
std::io::stdin().read_line(&mut input).expect("Failed to read input.");
let components: Vec<&str> = input.trim().split(' ').collect();
(components[0].to_string(), components[1].to_string())
}
fn read_query() -> Option<String> {
let mut input = String::new();
std::io::stdin().read_line(&mut input).expect("Failed to read input.");
if input.len() <= 0 {
None
} else {
Some(input.trim().to_string())
}
}
use std::collections::HashMap; 來做 local name binding。如果我們可以用先知道 Capacity 就可以用 HashMap::with_capacity(uint) 來創建，或者用 HashMap::new() 。而我們將 User input 讀入後存到 input ，但因為 input 是 String，所以要轉成數字。這裡用 i32::from_str() 來作轉換，記得要 use std::str::FromStr; ，為什麼呢？這裡要深究 Rust 中關於 Trait 的部分 ( FromStr 是一個 Trait)，詳情可以先參考 Rust 關於 Trait 的部分，這邊就暫時先忽略。再來我們看到 phone_book 是 HashMap<String, String> Type，並且是用 HashMap::new() 來初始化。read_entry 這個 Function，其回傳的 Type 是 Entry ，這是什麼呢？這是一個 alias type，實際上是上面定義的 (String, String) 這個 Tuple。而在這個 Function 一樣先把輸入存到 input ，再透過 input.trim().split(' ').collect() 得到一個 Vector of &str 。這邊因為 input.trim().split(' ') 得到的是一個 Iterator，所以要在 invoke collect() 才得到 Vector。而 &str 可以想成是一個不可變的 string。最後這個 Function 就回傳一個 Tuple，也就是我們所定義的 Alias Type Entry 。每次得到一個 Entry ，我們就把他分別存到 name 跟 number 並且透過 HashMap 的 insert Method 來把 Key ( name) 和 Value ( number) 存到 HashMap phone_book 。while ，每次先 Call read_query() 。read_query 做的事情很簡單，就是把要查詢的名字讀進來，如果 OK 就回傳 Some(<name>) 否則就是 None 。不過這裡有沒有發現多了一個 let ，這是 Rust 的 while let ，也就是當 read_query() 回傳是 None 時， Some(query) = read_query() 會是 False，於是就跳出 while 了，這是為了簡化我們本來應該要在 while 裡面去 match Option，如果是 None就跳出 while 這件事，可以參考這裡。而在這裡我們一並也把 Some(query) 中的 query 給取出來了。再來就是 match phone_book.get(&query) ，這裡給 &query 是 borrowing type (所有權問題)，而 phone_book.get(&query) 會得到 Option，所以這邊當 Option 是 Some(number) ，就表示有這個 Key，並把 K-V 印出來。但如果是 None 就是 Not found 啦！今天講的是 Map，大家的實作都差不多，但當然還是有一些不一樣的地方，包含細節的 Hash function 和解決 Collision 的方式，大家可以再深入研究。另外今天也對 Rust 又有更多了解了，哈哈哈！明天見！
iThome鐵人賽
看影片追技術